/*
    动态规划中根据数据量猜解法的技巧

    前置知识: 
    讲解043 - 根据数据量猜解法的技巧
    讲解066、067、068、069 - 动态规划基础
    讲解072 - 最长递增子序列
    讲解073 - 01背包
    【必备】课程的动态规划大专题从讲解066开始，建议从头开始学习会比较系统

    对于一个具体的题目，方法运行的指令条数不能超过10^7 ~ 10^8规模，否则就会超时
    那么就可以利用这个条件：
    1，想出能通过的方法再去实现
    2，确定优化做到什么程度才能通过

    ================================================

    题目1
    贿赂怪兽
    开始时你的能力是0，你的目标是从1号怪兽开始，通过所有的n只怪兽
    如果你当前的能力小于i号怪兽的能力，则必须付出b[i]的钱贿赂这个怪兽
    然后怪兽就会加入你，他的能力a[i]直接累加到你的能力上
    如果你当前的能力大于等于i号怪兽的能力，你可以选择直接通过，且能力不会下降
    但你依然可以选择贿赂这个怪兽，然后怪兽的能力直接累加到你的能力上
    返回通过所有的怪兽，需要花的最小钱数
    测试链接 : https://www.nowcoder.com/practice/736e12861f9746ab8ae064d4aae2d5a9

    进行如下的思考:
    假设a[i]数值的范围很大，但是b[i]数值的范围不大，该怎么做？
    假设a[i]数值的范围不大，但是b[i]数值的范围很大，又该怎么做？

    ================================================

    题目2
    选择k个数字使得两集合累加和相差不超过1
    给定一个正数n，表示1~n这些数字都可以选择
    给定一个正数k，表示要从1~n中选择k个数字组成集合A，剩下数字组成集合B
    希望做到集合A和集合B的累加和相差不超过1
    如果能做到，返回集合A选择了哪些数字，任何一种方案都可以
    如果不能做到，返回长度为0的数组
    2 <= n <= 10^6
    1 <= k <= n
    来自真实大厂笔试，没有测试链接，用对数器验证

    评估一下数据规模，01背包的解法可行吗？

    ================================================

    题目3
    两个排列的最长公共子序列长度
    给出由1~n这些数字组成的两个排列
    求它们的最长公共子序列长度
    n <= 10^5
    测试链接 : https://www.luogu.com.cn/problem/P1439

    评估一下数据规模，经典的求最长公共子序列的做法可行吗？

    ================================================

    题目4
    使数组严格递增的最小操作数
    给你两个整数数组 arr1 和 arr2
    返回使 arr1 严格递增所需要的最小操作数（可能为0）
    每一步操作中，你可以分别从 arr1 和 arr2 中各选出一个索引
    分别为 i 和 j，0 <= i < arr1.length 和 0 <= j < arr2.length
    然后进行赋值运算 arr1[i] = arr2[j]
    如果无法让 arr1 严格递增，请返回-1
    1 <= arr1.length, arr2.length <= 2000
    0 <= arr1[i], arr2[i] <= 10^9
    测试链接 : https://leetcode.cn/problems/make-array-strictly-increasing/

    评估一下数据规模，用数组中的值做可变参数可行吗？

*/